Thuật toán Karger là thuật toán ngẫu nhiên nhanh nhất hiện nay cho việc tìm lát cắt nhỏ nhất, với thời gian chạy O(|V|2 log3|V|). Để chứng minh điều này, tác giả chỉ ra cách thực hiện chuỗi các phép hợp nhất để giảm kích thước G {\displaystyle G} xuống ⌈ n / 2 + 1 ⌉ {\displaystyle \left\lceil n/{\sqrt {2}}+1\right\rceil } đỉnh trong thời gian O ( n 2 ) {\displaystyle O(n^{2})} . Do đó thời gian chạy của thuật toán là T ( n ) = 2 ( n 2 + T ( ⌈ n / 2 + 1 ⌉ ) ) {\displaystyle T(n)=2\left(n^{2}+T\left(\left\lceil n/{\sqrt {2}}+1\right\rceil \right)\right)} . Phương trình này cho kết quả T ( n ) = O ( n 2 l o g ( n ) ) {\displaystyle T(n)=O(n^{2}log(n))} . Sau mỗi lần thực hiện thuật toán, xác suất tìm ra lát cắt nhỏ nhất là Ω ( 1 / l o g ( n ) ) {\displaystyle \Omega (1/log(n))} . Nếu thực hiện thuật toán O ( l o g 2 ( n ) ) {\displaystyle O(log^{2}(n))} lần thì xác suất không tìm ra lát cắt nhỏ nhất giảm xuống O(1/n2).